/*
Date:20210418 14：47pm
key:1.首先是边上围上一圈哨兵，方便递归边界判断。
    2.其次走过的点直接置成题目中不会出现的字符即可，不需要通过set记录坐标。
*/
class Solution {
public:
    //打印矩阵
    void print_mat(vector<vector<char>>& board)
    {
        for(auto i:board)
            {for(auto j:i)
                {cout<<j<<" ";}
            cout<<endl;}
    }
    bool findstr(vector<vector<char>>& board,int i,int j,string&word,int k)
    {
        //终止条件
        if(k==word.size()){return true;}
        //如果不终止，继续的条件
        else
        {
            if(board[i][j]==word[k])
            {
                    //画龙点睛法，不需要set都可以完成。
                    char c=board[i][j];
                    //四个方向都可以
                    board[i][j]='0';
                    bool b;
                    //其实通常这一步是遍历实现，不过这里ij关系不好迭代得出，干脆直接写四个方向的式子。
                    b=((findstr(board,i-1,j,word,k+1))||findstr(board,i,j-1,word,k+1)|| findstr(board,i+1,j,word,k+1)||findstr(board,i,j+1,word,k+1));
                    board[i][j]=c;
                    return b;


                
            }
            //当前格子数字不匹配，直接暂停
            else
            {
                return false;
            }
        }
        
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) 
    {
        int i=board[0].size()+2;
        vector<char>sb;
        //制作首行和末行的哨兵节点
        while(i--)
        {
            sb.push_back('0');
        }
        //插入首行和末行的哨兵节点
        board.insert(board.begin(),sb);
        board.insert(board.end(),sb);
        //除首行和末行，其余头尾插入哨兵节点
        for(i=0;i<board.size();i++)
        {
            if(i==0||i==board.size()-1)
            {
                ;
            }
            else
            {
                board[i].insert(board[i].begin(),'0');
                board[i].insert(board[i].end(),'0');
            }
        }
        //至此新矩阵制作完成
        //在新矩阵里读旧矩阵
        int k=0;//统计符合已知字符串的最新下标
        set<vector<int>>setij;

        for(i=1;i<board.size()-1;i++)
            {for(int j=1;j<board[i].size()-1;j++)
                {
                    if(findstr(board,i,j,word,k))
                    {
                        return true;
                    }
                    else
                    {
                        //重置k
                        k=0;
                    }
                }
            cout<<"\n";
            }
        //print_mat(board);


        return false;
    }
};